<?php
/**
 * PHP树形结构操作
 * 
 * $Id: tree.functions.php 122 2010-05-28 10:05:16Z Administrator $
 * $Revision: 122 $
 * $Author: Administrator $
 * $Date: 2010-05-28 18:05:16 +0800 (星期五, 28 五月 2010) $
 * 本涵数库，可以通过一次数据库读取，将数据库里通过ID->父ID保存的树形数据格式成各种树形。
 * 目前支持的转换的树形有:<br />
 * 平面树->立体树<br />
 * 立体树->UI，LI HTML输出<br />
 * 立体树->适合SELECT列出的树(也适合Smarty循环)，<br />
 * 适合SELECT列出的树->移除某ID和他的子树<br />
 * 适合SELECT列出的树->取得某ID和他的子树<br />
 * <br />
 * 经过转换后的树形增加了叶结点的判断，当前结点的深度(根从0开始)。<br />
 * 
 * 
 * @author glzaboy<glzaboy@163.com>
 * @package fastlib
 * @subpackage functions
 * @copyright 2005-2010 (c) glzaboy
 */
if (! defined ( '__FASTLIB__' )) {
	if (__DEBUG__) {
		die ( sprintf ( 'Forbidden 403 at file %s on line %d', __FILE__, __LINE__ ) );
	} else {
		die ( 'Forbidden 403' );
	}
}
/**
 * UILI的一个示例
 *
 * 直接输出成HTML格式的树形
 * 
 * 代码实例，可以做适当的更改。
 * <code>
 *	function treeParser ($treeData, $show = array('name'=>'name','section'=>'ul','item'=>'li'))
 *	{
 *	    $treeNode = "";
 *	    if (is_array($treeData)) {
 *	        foreach ($treeData as $v) {
 *	            if ($v['child']) {
 *	                $treeNode .= "<{$show['item']}><a href=\"{$v['url']}\">{$v[$show['name']]}</a>";
 *	                $treeNode .= '<div>'.treeParser($v['child']).'</div>';
 *	                $treeNode .="</{$show['item']}>";
 *	            } else {
 *	                $treeNode .= "<{$show['item']}><a href=\"{$v['url']}\">{$v[$show['name']]}</a></{$show['item']}>";
 *	            }
 *	        }
 *	    }
 *	    return '<' . $show['section'] . '>' . $treeNode . '</' . $show['section'] . '>';
 *	}
 * </code>
 * 
 * 
 * 
 * @param Array $treeData 由treeGet得到的结果
 * @param Array $show 字段映射，其中section是有子结点的结点使用的标签，item是没有结点的标签
 * @return String HTML
 */
function treeParser ($treeData, $show = array('name'=>'name','section'=>'ul','item'=>'li'))
{
    $treeNode = "";
    if (is_array($treeData)) {
        foreach ($treeData as $v) {
            if ($v['child']) {
                $treeNode .= "<{$show['item']}><a href=\"{$v['url']}\">{$v[$show['name']]}</a>";
                $treeNode .= '<div>'.treeParser($v['child']).'</div>';
                $treeNode .="</{$show['item']}>";
            } else {
                $treeNode .= "<{$show['item']}><a href=\"{$v['url']}\">{$v[$show['name']]}</a></{$show['item']}>";
            }
        }
    }
    return '<' . $show['section'] . '>' . $treeNode . '</' . $show['section'] . '>';
}
/**
 * 树形路径
 *
 * @param  Array	$tree	树形数据从treeList得到的数据
 * @param  int		$id 	查询的结点ID
 * @param  Array	$field   数据选项array('deepValue'=>'deepValue','deep'=>'deep')
 * @return Array	数组
 */
function treePath($tree, $id, $field = array('id'=>'id','deep'=>'deep')) {
	if (! $field ['id']) {
		$field ['id'] = 'id';
	}
	if (! $field ['deep']) {
		$field ['deep'] = 'deep';
	}
	$mytree = array_reverse ( $tree, true );
	$path = array ();
	$mydeep = null;
	foreach ( $mytree as $v ) {
		if ($v [$field ['id']] == $id) {
			$mydeep = $v [$field ['deep']];
			array_push ( $path, $v );
			continue;
		}
		if ($v [$field ['deep']] < $mydeep) {
			$mydeep --;
			array_unshift ( $path, $v );
		}
	}
	return $path;
}
/**
 * 选择或移除树形中的部分
 *
 * @param  Array	$tree		树形数据从treeList得到的数据
 * @param  int		$id 		选择或移除的树形ID
 * @param  String	$option	选项remove/Select
 * @param  Array	$field   数据选项array('deepValue'=>'deepValue','deep'=>'deep')
 * @return Array	数组
 */
function treeFilter($tree, $id, $option = "remove", $field = array('deepValue'=>'deepValue','deep'=>'deep')) {
	if (! $field ['deepValue']) {
		$field ['deepValue'] = "deepValue";
	}
	if (! $field ['deep']) {
		$field ['deep'] = "deep";
	}
	switch (strtolower ( $option )) {
		case "select" :
			$tmpTree = array ();
			$mydeep = - 1;
			foreach ( $tree as $v ) {
				if ($id == $v ['id']) {
					$mydeep = $v [$field ['deep']];
					if ($mydeep > 0) {
						$v [$field ['deepValue']] = preg_replace ( "/^┃{" . $mydeep . "}/", '', $v [$field ['deepValue']] );
						$v [$field ['deep']] = $v [$field ['deep']] - $mydeep; //修正新的深度
					}
					array_push ( $tmpTree, $v );
				} elseif ($mydeep != - 1) {
					if ($v [$field ['deep']] <= $mydeep) {
						break;
					} else {
						if ($mydeep > 0) {
							$v [$field ['deepValue']] = preg_replace ( "/^┃{" . $mydeep . "}/", '', $v [$field ['deepValue']] );
							$v [$field ['deep']] = $v [$field ['deep']] - $mydeep; //修正新的深度
						}
						array_push ( $tmpTree, $v );
					}
				}
			}
			break;
		case "remove" :
		default :
			$tmpTree = array ();
			$mydeep = - 1;
			foreach ( $tree as $v ) {
				if ($id == $v ['id']) {
					$mydeep = $v [$field ['deep']];
					continue;
				} elseif ($mydeep != - 1) {
					if ($v [$field ['deep']] <= $mydeep) {
						array_push ( $tmpTree, $v );
						$mydeep = - 1;
					}
					continue;
				}
				array_push ( $tmpTree, $v );
			}
	}
	return $tmpTree;
}
/**
 * 返回一个可以用于SELECT和列表数组　
 *
 * @param  Array	$treeData   从treeGet得到的数据
 * @param  Array	$List   返回结果的数据 
 * @param  Array	$field   数据选项array('deepValue'=>'deepValue','deep'=>'deep','child'=>'child')
 * @return Array	数组
 */
function treeList($treeData, &$List, $field = array('deepValue'=>'deepValue','deep'=>'deep','child'=>'child')) {
	if (! $field ['deepValue']) {
		$field ['deepValue'] = "deepValue";
	}
	if (! $field ['deep']) {
		$field ['deep'] = "deep";
	}
	if (! $field ['child']) {
		$field ['child'] = "child";
	}
	static $mydeep = 0;
	if (is_array ( $treeData )) {
		foreach ( $treeData as $v ) {
			$v [$field ['deepValue']] = treeMakeDeep ( $mydeep );
			$v [$field ['deep']] = $mydeep;
			$t = $v;
			unset ( $t [$field ['child']] );
			array_push ( $List, $t );
			if (@$v [$field ['child']]) {
				++ $mydeep;
				treeList ( $v [$field ['child']], $List, $field );
				$mydeep --;
			}
		}
		$lastItem = array_pop ( $List ); //最后的一个元素
		if ($lastItem) { //空数组的情况
			$lastItem [$field ['deepValue']] = str_replace ( '┣', '┗', $lastItem [$field ['deepValue']] );
			array_push ( $List, $lastItem );
		}
		unset ( $lastItem );
	}
}
/**
 * 产生树结点深度
 *
 * @param  Array	$deep   深度
 * @return String	深度字串
 */
function treeMakeDeep($deep) {
	$returnValue = "";
	for(; $deep; $deep --) {
		$returnValue .= "┃";
	}
	return $returnValue . "┣";
}
/**
 * 将平面树转换成立体数
 *
 * @param  Array	$data   数据源
 * @param  Array	$field   数据选项array('fid'=>'fid','id'=>'id','child'=>'child','leaf'=>'leaf')
 * @return String	深度字串
 */
function treeGet($data, $field = array('fid'=>'fid','id'=>'id','child'=>'child','leaf'=>'leaf')) {
	$tmptree = null;
	$tree = $data;
	if (! $field ['child']) {
		$field ['child'] = "child";
	}
	if (! $field ['fid']) {
		$field ['fid'] = "fid";
	}
	if (! $field ['id']) {
		$field ['id'] = "id";
	}
	if (! $field ['leaf']) {
		$field ['leaf'] = "leaf";
	}
	return treeAddNodeToTree ( $tmptree, treegetbyuid ( $tree, 0, $field ), $tree, $field );
}
/**
 * 将平面的树形整理成立体树形
 *
 * 本函数供tree get调用不能直接调用
 * 
 * @param object $Node 加到的结点
 * @param Array $miniTree 取得的子树
 * @param Array $source 数据源
 * @param Array $field 字段映射
 * @return Array 整理好的立体树
 */
function treeAddNodeToTree($Node, $miniTree, &$source, $field) {
	if (is_array ( $miniTree )) {
		foreach ( $miniTree as $k => $v ) {
			if (! count ( $miniTree [$k] [$field ['child']] = treeAddNodeToTree ( $miniTree [$k], treegetbyuid ( $source, @$v [$field ['id']], $field ), $source, $field ) )) {
				unset ( $miniTree [$k] [$field ['child']] );
				$miniTree [$k] [$field ['leaf']] = true; //设置叶结点
			}
		}
		return $Node [$field ['child']] = $miniTree;
	}
	return null;
}
/**
 * 取得指定ID的子级并从$stree多移除所取得的记录
 *
 * 不直接调用本函数
 * 
 * @param Array $stree 
 * @param Int $uid 父ID
 * @param Array $field 字段映射只要一个fid
 * @return Array 所取得的记录
 */
function treegetbyuid(&$stree, $uid, $field) {
	$dtree = array ();
	if (is_array ( $stree )) {
		foreach ( $stree as $k => $v ) {
			if ($v [$field ['fid']] == $uid) {
				$mytmp = array ();
				$mytmp = $v;
				unset ( $stree [$k] );
				array_push ( $dtree, $mytmp );
				$mytmp = null;
			}
		}
	}
	return $dtree;
}
/**
 * 返回本模块信息
 *
 * @return string
 */
function treeprintInfo() {
	$version = '$Revision: 122 $';
	$moudle = explode ( "functions", __FILE__ );
	$moudle = $moudle [1] ? substr ( $moudle [1], 1 ) . 'functions' : $moudle;
	$return = '';
	$return .= startTable ();
	$return .= printRow ( array (array ('class' => 'h', 'content' => '<center>' . $moudle . '</center>', 'colspan' => '2' ) ) );
	$return .= printRow ( array (array ('class' => 'e', 'content' => 'author' ), array ('class' => 'v', 'content' => 'glzaboy' ) ) );
	$return .= printRow ( array (array ('class' => 'e', 'content' => 'version' ), array ('class' => 'v', 'content' => $version ) ) );
	$return .= endTable ();
	return $return;
}